package com.sheng.leetcode.year2022.month05.day19;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/05/20
 *
 * 453. 最小操作次数使数组元素相等
 *
 * 给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：3
 * 解释：
 * 只需要3次操作（注意每次操作会增加两个元素的值）：
 * [1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]
 * 示例 2：
 *
 * 输入：nums = [1,1,1]
 * 输出：0
 *
 * 提示：
 *
 * n == nums.length
 * 1 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * 答案保证符合 32-bit 整数
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-moves-to-equal-array-elements
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0453 {

    @Test
    public void test01(){
        int[] nums = {1,2,3};
//        int[] nums = {1,1,1};
        System.out.println(new Solution1().minMoves(nums));
    }
}
class Solution1 {
    //参考解法一：排序，然后每个数和最小数的差相加即可
//    public int minMoves(int[] nums) {
//        int count = 0;
//        Arrays.sort(nums);
//        for (int i = nums.length - 1; i > 0; i--) {
//            count += nums[i] - nums[0];
//        }
//        return count;
//    }

    //二：首先，假设执行过程无误，则设数组操作前最小值为min，最大值为max，共需操作k次，
    //操作前数组总和为sum。分析得知，每次从数组中找出最小的两个值并分别加一，
    //则每次使 sum 加上（n-1），则执行 k 次共使 sum 加 k *（n-1），
    //即执行结束时数组总和为 sum + k*（n-1）。从另一方面由贪心算法得知，
    //经过 k 步后原数组最小值 min 变为 min+k，此时数组所有值均为 min+k，则数组和为 n*（min+k）。
    //故得等式 sum+k*（n-1） = n*（min+k），化简得 k = sum-n*min，求解完成。
    public int minMoves(int[] nums) {
        int sum = 0;
        int n = nums.length;
        Arrays.sort(nums);
        int min = nums[0];
        for (int i = 0; i < n; i++) {
            sum += nums[i];
        }
        return sum - n * min;
    }
}
